package 我的Java学习_算法基础.day_03;

import java.util.Arrays;

public class _054_需排序的子数组长度是多少 {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6};
        int[] b =findSegment(a,a.length);
        System.out.println(Arrays.toString(b));
        a =new int[] {1,5,3,4,2,6,7};
        b =findSegment(a,a.length);
        System.out.println(Arrays.toString(b));
        a =new int[] {2,3,7,5,4,6};
        b =findSegment(a,a.length);
        System.out.println(Arrays.toString(b));
        a =new int[] {3,2,5,6,7,8};
        b =findSegment(a,a.length);
        System.out.println(Arrays.toString(b));
        a =new int[] {2,8,7,10,9};
        b =findSegment(a,a.length);
        System.out.println(Arrays.toString(b));
        a =new int[] {2,3,7,4,1,5,6};
        b =findSegment(a,a.length);
        System.out.println(Arrays.toString(b));

    }
    public static int[] findSegment(int[] array,int n){
        int left = -1,right =-1;
        int max = array[0],min = array[n-1];
        //拓展右端点：更新历史最高，只要右侧出现比历史最高低的，右边界就扩展到此处
        for(int i = 0;i<n;i++){
            if(array[i]>max)
                max = array[i];
            //只要低于历史高峰，就要拓展排序区间的右端点
            if(array[i]<max){
                right = i;
            }
        }
        //拓展左端点：更新历史最低，只要左侧出现比历史最低高的，就要将左边界扩展到此处
        for(int i =n-1;i>=0;i--){
            if(array[i]<min)
                min = array[i];
            if(array[i]>min)
                left = i;

        }
        if(left==-1){
            return new int[]{0,0};
        }
        return new int[]{left,right};
    }
}
